<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
	<META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=utf-8">
	<TITLE></TITLE>
	<META NAME="GENERATOR" CONTENT="OpenOffice.org 3.3  (Unix)">
	<META NAME="AUTHOR" CONTENT="Eloi Puertas Prats">
	<META NAME="CREATED" CONTENT="20111003;11143100">
	<META NAME="CHANGEDBY" CONTENT="Eloi Puertas Prats">
	<META NAME="CHANGED" CONTENT="20111003;13003500">
</HEAD>
<BODY LANG="ca-ES" DIR="LTR">
<P STYLE="margin-bottom: 0cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=5><B>Projecte
2: Cerca dins del món Menjaclosques d'en Pacman</B></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><IMG SRC="maze.png" NAME="graphics1" ALIGN=LEFT WIDTH=356 HEIGHT=352 BORDER=0><BR CLEAR=LEFT><BR><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.49cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=4><B>Introducció</B></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm; font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>En
aquest projecte, el vostre agent Pacman trobarà camins a través del
seu laberíntic món, tant per arribar a una determinada posició com
per recollir el menjar de forma eficient. Heu de construir algorismes
de cerca generals i aplicar-los als escenaris de Pacman.</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-weight: normal">El
codi per a aquest projecte consisteix en diversos fitxers Python,
alguns dels quals haureu de llegir i comprendre de cara a completar
el projecte i alguns dels quals podeu ignorar. Podeu descarregar el
codi i els fitxers de suport </SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/search.zip"><FONT COLOR="#002ce2"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><U><SPAN STYLE="font-weight: normal">aquí</SPAN></U></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-weight: normal">.</SPAN></FONT></FONT></FONT></P>
<TABLE WIDTH=680 BORDER=0 CELLPADDING=8 CELLSPACING=0>
	<COL WIDTH=328>
	<COL WIDTH=320>
	<TR>
		<TD COLSPAN=2 WIDTH=664>
			<P ALIGN=LEFT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><B>Fitxers
			que heu editar:</B></FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD WIDTH=328>
			<P ALIGN=LEFT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/search.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">search.py</SPAN></FONT></FONT></FONT></A></P>
		</TD>
		<TD WIDTH=320>
			<P ALIGN=LEFT STYLE="font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>En
			el qual residiran tots els vostres algorismes de cerca.</FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD WIDTH=328>
			<P ALIGN=LEFT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/searchAgents.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">searchAgents.py</SPAN></FONT></FONT></FONT></A></P>
		</TD>
		<TD WIDTH=320>
			<P ALIGN=LEFT STYLE="font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>En
			el qual residiran tots els vostres agents cercadors.</FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD COLSPAN=2 WIDTH=664>
			<P ALIGN=LEFT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><B>Fitxers
			que és interessant que entengueu:</B></FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD WIDTH=328>
			<P ALIGN=LEFT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/pacman.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">pacman.py</SPAN></FONT></FONT></FONT></A></P>
		</TD>
		<TD WIDTH=320>
			<P ALIGN=LEFT STYLE="font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Fitxer
			principal que executa els jocs de Pacman. Aquest fitxer descriu un
			tipus GameState, que podeu utilitzar en aquest projecte.</FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD WIDTH=328>
			<P ALIGN=LEFT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/game.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">game.py</SPAN></FONT></FONT></FONT></A></P>
		</TD>
		<TD WIDTH=320>
			<P ALIGN=LEFT STYLE="font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>La
			lògica que controla com funciona el món de Pacman. Aquest fitxer
			descriu diversos tipus de suport com AgentState, Agent, Direction
			i Grid.</FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD WIDTH=328>
			<P ALIGN=LEFT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/util.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">util.py</SPAN></FONT></FONT></FONT></A></P>
		</TD>
		<TD WIDTH=320>
			<P ALIGN=LEFT STYLE="font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Estructures
			de dades útils per implementar algorismes de cerca.</FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD COLSPAN=2 WIDTH=664>
			<P ALIGN=LEFT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><B>Fitxers
			que no cal que entengueu:</B></FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD WIDTH=328>
			<P ALIGN=LEFT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/graphicsDisplay.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">graphicsDisplay.py</SPAN></FONT></FONT></FONT></A></P>
		</TD>
		<TD WIDTH=320>
			<P ALIGN=LEFT STYLE="font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Gràfics
			del Pacman</FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD WIDTH=328>
			<P ALIGN=LEFT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/graphicsUtils.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">graphicsUtils.py</SPAN></FONT></FONT></FONT></A></P>
		</TD>
		<TD WIDTH=320>
			<P ALIGN=LEFT STYLE="font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Suport
			per als gràfics del Pacman</FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD WIDTH=328>
			<P ALIGN=LEFT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/textDisplay.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">textDisplay.py</SPAN></FONT></FONT></FONT></A></P>
		</TD>
		<TD WIDTH=320>
			<P ALIGN=LEFT STYLE="font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Gràfics
			ASCII del Pacman</FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD WIDTH=328>
			<P ALIGN=LEFT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/ghostAgents.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">ghostAgents.py</SPAN></FONT></FONT></FONT></A></P>
		</TD>
		<TD WIDTH=320>
			<P ALIGN=LEFT STYLE="font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Agents
			per controlar els fantasmes</FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD WIDTH=328>
			<P ALIGN=LEFT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/keyboardAgents.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">keyboardAgents.py</SPAN></FONT></FONT></FONT></A></P>
		</TD>
		<TD WIDTH=320>
			<P ALIGN=LEFT STYLE="font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Interfície
			teclat per controlar Pacman</FONT></FONT></FONT></P>
		</TD>
	</TR>
	<TR>
		<TD WIDTH=328>
			<P ALIGN=LEFT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/layout.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">layout.py</SPAN></FONT></FONT></FONT></A></P>
		</TD>
		<TD WIDTH=320>
			<P ALIGN=LEFT STYLE="font-weight: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Codi
			per llegir els fitxers de layout i guardar els seus continguts.</FONT></FONT></FONT></P>
		</TD>
	</TR>
</TABLE>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"> </FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><B>Què
heu d'enviar?:</B></FONT></FONT></FONT><FONT COLOR="#000000">
Omplireu </FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-weight: normal">fragments
de </SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/search.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">search.py</SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-weight: normal">i
</SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/searchAgents.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-weight: normal">searchAgents.py</SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-weight: normal">durant
el projecte. Heu d'enviar únicament aquests dos fitxers (juntament
amb un document descriptiu del treball realitzat) en un. Tar.gz. a
través del campus virtual.</SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.49cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=4><B>Benvinguts
a Pacman</B></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-weight: normal">Després
de baixar </SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/search.zip"><FONT COLOR="#002ce2"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><U><SPAN STYLE="font-weight: normal">el
codi</SPAN></U></FONT></FONT></FONT></A><FONT COLOR="#000000"> </FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-weight: normal">,
descomprimir-lo i entrar al directori </SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><SPAN STYLE="font-weight: normal">search,
</SPAN></I></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">hauríeu
de poder jugar una partida de Pacman escrivint en la línia de
comandes:</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
pacman.py </FONT></FONT></FONT>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>El
primer pas per en Pacman serà ser capaç de navegar en el seu món
de forma eficient.</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">L'agent
més senzill en </SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/searchAgents.html"><FONT COLOR="#002ce2"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><U><SPAN STYLE="font-weight: normal">searchAgents.py</SPAN></U></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">es
diu </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">GoWestAgent</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">,
i sempre va cap a l'Oest (és un agent reactiu trivial). Aquest agent
pot guanyar en alguna ocasió:</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
pacman.py - layout testMaze - Pacman GoWestAgent </FONT></FONT></FONT>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Però
quan cal girar, les coses es posen lletges:</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
pacman.py - layout tinyMaze - Pacman GoWestAgent </FONT></FONT></FONT>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Aviat,
el vostre agent resoldrà no només </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">tinyMaze</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">,
sinó qualsevol altre laberint que vulgueu. Observeu que </SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/pacman.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">pacman.py</SPAN></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">suporta
un nombre d'opcions que es poden expressar d'una forma llarga (pe,
</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">--layout</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">)
o d'una forma curta (pe, </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">-l</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">).
Podeu visualitzar la llista de totes les opcions i els seus valors
per defecte mitjançant:</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
pacman.py-h </FONT></FONT></FONT>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Tots
els comandaments que apareixen en aquest projecte apareixen també en
</SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/commands.txt"><FONT COLOR="#002ce2"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><U><SPAN STYLE="font-weight: normal">commands.txt</SPAN></U></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">,
perquè us sigui més senzill el copiar i enganxar. Fins i tot
podríeu executar tots seguits si volguéssiu amb la instrucció </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">bash
commands.txt</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">.</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.49cm; font-style: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=4><B>Trobant
un Floc de Menjar Fix utilitzant Algorismes de Cerca</B></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">En
</SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/searchAgents.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">searchAgents.py</SPAN></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">,
trobareu un </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">SearchAgent</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">,
completament implementat que planeja el seu camí a través del món
de Pacman i després executa el camí pas a pas. Els algorismes de
cerca per formular un pla no estan implementats - aquest és el
vostre treball. A mesura que avanceu al llarg de les següents
preguntes, potser necessitareu consultar aquest </SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/searchCat1#Glossary"><FONT COLOR="#002ce2"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><U><SPAN STYLE="font-weight: normal">glossari
d'objectes en el codi</SPAN></U></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">.
En primer lloc, verificar que el </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">SearchAgent</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">funciona
correctament executant:</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
pacman.py-l tinyMaze-p SearchAgent-a fn = tinyMazeSearch </FONT></FONT></FONT>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">La
comanda indica al </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">SearchAgent</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">que
utilitzi </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">tinyMazeSearch</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">com
el seu algorisme de cerca. </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">tinyMazeSearch
</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Times New Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">està
implementat en</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/search.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><U><SPAN STYLE="font-weight: normal">search.py</SPAN></U></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">.
Pacman hauria de navegar pel laberint amb èxit.</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Ara
ha arribat el moment d'implementar funcions de cerca genèriques per
ajudar a en Pacman a planificar les seves rutes. El pseudocodi per
als algorismes que heu d'escriure els podeu trobar a les
transparències de teoria i en el llibre. Recordeu que un node de
recerca no ha de contenir únicament un estat sinó també la
informació necessària per reconstruir el camí (pla) que el porti a
aquest estat.</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><SPAN STYLE="font-weight: normal">Nota
important;</SPAN></I></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Totes
les vostres funcions de cerca han de retornar una llista </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><SPAN STYLE="font-weight: normal">d'accions</SPAN></I></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">que
portin a l'agent des de l'inici fins l'objectiu. Aquestes accions han
de ser moviments legals (adreces vàlides, no ens podem moure
travessant murs).</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><SPAN STYLE="font-weight: normal">Ajuda:</SPAN></I></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Tots
els algorismes són molt similars. Els algorismes per DFS, BFS, UCS,
i A * es diferencien tan sols en els detalls de com es gestiona la
frontera. Per tant, concentreu-vos en implementar DFS bé i la resta
hauria de ser relativament fàcil. De fet, una possible implementació
només necessitaria d'una funció genèrica de recerca que es
configurés en cada cas amb un estratègia d'encuament diferent (la
vostra implementació no té perquè ser així).</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><SPAN STYLE="font-weight: normal">Ajuda:</SPAN></I></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Assegureu-vos
d'entendre bé les classes </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Stack,
Queue</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"> </FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">i
</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">PriorityQueue</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">posades
a la vostra disposició en </SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/util.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">util.py</SPAN></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">!</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><B>Qüestió
1:</B></I></FONT></FONT></FONT><FONT COLOR="#000000"> </FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Implementeu
l'algorisme de cerca de profunditat prioritària en la funció
</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">depthFirstSearch</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">en
</SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/search.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">search.py</SPAN></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">.
Per fer que el vostre algorisme sigui </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><SPAN STYLE="font-weight: normal">complet,</SPAN></I></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">codifiqueu
la versió de DFS que realitza recerca en un graf, evitant expandir
estats ja visitats (llibre de text secció 3.5).</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>El
vostre codi hauria de trobar fàcilment una solució per:</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
pacman.py-l tinyMaze-p SearchAgent</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
pacman.py-l mediumMaze-p SearchAgent</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
pacman.py-l bigMaze-z 0,5-p SearchAgent </FONT></FONT></FONT>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>El
tauler de Pacman us mostrarà com es van explorant els estats.
Vermell brillant significa els estats explorats primerament. Segueix
l'ordre d'exploració que haguéssiu esperat? En Pacman passa per
tots les caselles explorades quan segueix el seu camí cap a
l'objectiu?</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><SPAN STYLE="font-weight: normal">Ajuda:</SPAN></I></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Si
utilitzeu un </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Stack</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">com
a estructura de dades, la solució trobada pel vostre algorisme DFS
per </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">mediumMaze</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">hauria
de tenir una longitud de 130 (suposant que afegiu els successors a la
frontera en l'ordre en que ens els dóna getSuccessors; podríeu
obtenir 244 si els afegiu en ordre invers). És una solució de cost
mínim? En cas de no ser així, què està fent malament la recerca
primer en profunditat?</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><B>Qüestió
2:</B></I></FONT></FONT></FONT><FONT COLOR="#000000"> </FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Implementa
l'algorisme de cerca Amplitud prioritària (BFS) en la funció
</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">breadthFirstSearch</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">en
</SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/search.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">search.py</SPAN></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">.
De nou, escriviu l'algorisme que realitzi la cerca en grafs, evitant
expandir estats ja visitats. Verifiqueu el vostre codi de la mateixa
manera que ho vau fer per a la recerca primer en profunditat.</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
pacman.py-l mediumMaze-p SearchAgent-a fn = BFS</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
pacman.py-l bigMaze-p SearchAgent-a fn = BFS-z 5 </FONT></FONT></FONT>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Troba
BFS una solució de cost mínim? Si no, verifiqueu la vostra
implementació.</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><SPAN STYLE="font-weight: normal">Ajuda:</SPAN></I></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Si
en Pacman es mou lentament, proveu l'opció </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">--frameTime
0</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"> </FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">.</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><SPAN STYLE="font-weight: normal">Nota:</SPAN></I></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Si
heu escrit el codi de cerca de forma genèrica, el vostre codi hauria
de funcionar també amb el problema de cerca del 8-puzzle (llibre de
text secció 3.2) sense que hageu de realitzar cap canvi.</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
eightpuzzle.py </FONT></FONT></FONT>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.49cm"><BR><BR>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.49cm; font-style: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=4><B>Cerca
A *</B></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><I><B>Qüestió
3:</B></I></FONT></FONT></FONT><FONT COLOR="#000000"> </FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Implementeu
la recerca en grafs A * en la funció buida </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">aStarSearch</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">en
</SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/search.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">search.py</SPAN></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">.
A * ha de rebre una funció heurística com a paràmetre. La
heurística rep dos paràmetres: un estat del problema de recerca (el
paràmetre principal) i el problema en si mateix (com a informació
de referència, podria fer falta en algun cas). La funció heurística
</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">nullHeuristic</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">en
</SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/search.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">search.py</SPAN></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">és
un exemple trivial.</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Podeu
provar la implementació d'A * en el problema de trobar el camí en
un laberint fins a una posició fixa utilitzant com heurística la
distància Manhattan (heurística ja implementada com
</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">manhattanHeuristic</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">en
</SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/searchAgents.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">searchAgents.py</SPAN></SPAN></FONT></FONT></FONT></A><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">).</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>python
pacman.py-l bigMaze-z 0,5-p SearchAgent-a fn = ASTAR, Heuristic =
manhattanHeuristic. <FONT FACE="Times-Roman, serif">Què passa a
openMaze per les diferents estratègies de cerca?</FONT></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.49cm; font-style: normal"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=4><B>Glossari
de Objectes</B></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0.42cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Aquí
teniu un glossari dels objectes clau en el codi que estan relacionats
amb problemes de cerca::</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>SearchProblem
(search.py)</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Un
SearchProblem és un objecte abstracte que representa l'espai
d'estats, la funció successor, costos i estat objectiu d'un
problema. Interactuareu amb qualsevol SearchProblem únicament a
través dels mètodes definits en la part superior de </SPAN></SPAN></FONT></FONT></FONT><A HREF="http://campusvirtual.ub.edu/file.php/28269/curso2011-12/laboratorio/search/docs/search.html"><FONT COLOR="#002ce2"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">search.py</SPAN></SPAN></FONT></FONT></FONT></A></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>PositionSearchProblem
(searchAgents.py)</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-left: 2cm; margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Un
tipus de SearchProblem específic amb el qual treballareu - correspon
a buscar un únic floc en un laberint.</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>CornersProblem
(searchAgents.py)</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-left: 2cm; margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Un
tipus de SearchProblem específic que definireu - correspon a buscar
un camí que passi per les quatre cantonades d'un laberint.</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>FoodSearchProblem
(searchAgents.py)</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-left: 2cm; margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Un
tipus de SearchProblem específic amb el qual treballareu - correspon
a cercar la manera de menjar-se tots els flocs d'un laberint.</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3>Search
Function</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">Una
funció de cerca és una funció que pren com a paràmetre una
instància de SearchProblem, corre algun algorisme i retorna una
seqüència d'accions que condueixen a l'objectiu. Exemples de
funcions de cerca són </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">depthFirstSearch</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">i
</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">breadthFirstSearch</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">,
que heu d'escriure. S'inclou  </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">tinyMazeSearch</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">que
és una funció de cerca molt dolenta que només funciona
correctament en </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">tinyMaze.</SPAN></SPAN></FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; font-style: normal; font-weight: normal">
<FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3>SearchAgent</FONT></FONT></FONT></P>
<P ALIGN=LEFT STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">SearchAgent</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">és
una classe que implementa un Agent (un objecte que interactua amb el
món) i realitza la seva planificació a través d'una funció de
cerca. El </SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000"><FONT FACE="Courier, monospace"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">SearchAgent</SPAN></SPAN></FONT></FONT></FONT><FONT COLOR="#000000">
</FONT><FONT COLOR="#000000"><FONT FACE="Times-Roman, serif"><FONT SIZE=3><SPAN STYLE="font-style: normal"><SPAN STYLE="font-weight: normal">utilitza
en primer lloc la funció de cerca rebuda per realitzar un pla de les
accions necessàries per aconseguir l'estat objectiu i, a
continuació, executa les accions una a una.</SPAN></SPAN></FONT></FONT></FONT></P>
</BODY>
</HTML>
